#include "multiway_merge.h"  // 引入 heapmerge::merge_runs 声明

#include <algorithm>  // std::sort / std::is_sorted
#include <iostream>   // std::cout
#include <random>     // std::mt19937 / std::uniform_int_distribution
#include <vector>     // std::vector

int main() {
    using Record = int;                // 以 int 作为示例记录类型
    using File   = std::vector<Record>;

    constexpr std::size_t files_count      = 5;   // 模拟 5 个 run
    constexpr std::size_t records_per_file = 10;  // 每个 run 10 条记录

    std::mt19937 rng{42};                        // 固定种子，保证结果可复现
    std::uniform_int_distribution<int> dist(0, 100); // 均匀分布随机数

    std::vector<File> runs;
    runs.reserve(files_count);                   // 预留容量避免扩容

    for (std::size_t i = 0; i < files_count; ++i) {
        File f;
        f.reserve(records_per_file);             // 每个 run 预留大小
        const int base = static_cast<int>(i * 100); // 让各 run 数值区间错开，便于观察
        for (std::size_t j = 0; j < records_per_file; ++j) {
            f.push_back(base + dist(rng));       // 生成随机数
        }
        std::sort(f.begin(), f.end());           // run 内部排序
        runs.push_back(std::move(f));            // 收集有序 run
    }

    File merged = heapmerge::merge_runs(runs);   // 使用多路归并合并所有 run

    std::cout << "Merged sequence (" << merged.size() << " records):\n";
    for (std::size_t i = 0; i < merged.size(); ++i) {
        std::cout << merged[i] << (i + 1 == merged.size() ? '\n' : ' '); // 打印结果
    }

    if (std::is_sorted(merged.begin(), merged.end())) {   // 校验结果是否升序
        std::cout << "Verification passed: sequence is sorted.\n";
    } else {
        std::cout << "Verification FAILED!\n";
    }
    return 0;
}